Năm 1989, sau khi tốt nghiệp Lục quân Nam Xương, Phương Vĩnh Tường chính thức nhập ngũ Quân Giải phóng Nhân dân Trung Quốc, phân về phục vụ ở Quân khu Nam Kinh. Trong những năm đầu, ông hoạt động trong Tập đoàn quân 31, lần lượt là Trung đội trưởng, Đại đội trưởng, Chính ủy Tiểu đoàn, cán bộ Khoa Tổ chức phụ trách giáo dục chính trị, rồi Chủ nhiệm Phòng Chính trị của Trung đoàn. Tháng 3 năm 2002, ông nhậm chức Chính ủy Trung đoàn Tăng thiết giáp thuộc Sư đoàn 91, đi học thạc sĩ 2 năm rồi trở về giữ chức Chủ nhiệm Bộ Chính trị Lữ đoàn của Sư đoàn 91 và Chính ủy Lữ đoàn 92.[1] Đến năm 2010, ông là Chính ủy Sư đoàn 86 của Tập đoàn quân 31, giữ chức này hơn 4 năm thì được điều tới Tập đoàn quân 1 làm Chủ nhiệm Bộ Chính trị của tập đoàn quân này. Sang tháng 6 năm 2015, ông được điều lên Tổng bộ Chính trị Quân Giải phóng Nhân dân Trung Quốc, giữ chức Bộ trưởng Bộ thứ 2, được phong quân hàm Thiếu tướng Lục quân vào thời điểm này. Đến đầu năm 2016, hệ thống tổ chức quân đội được cải tổ, ông được điều về Chiến khu Đông Bộ, nhậm chức Phó Chủ nhiệm Bộ Công tác chính trị của Lục quân chiến khu.[1] Sang tháng 4 năm 2017, ông được bổ nhiệm làm Chính ủy Tập đoàn quân 81, một tập đoàn quân thuộc Chiến khu Trung Bộ và Lục quân Trung Quốc.[2]

Ngay 17 tháng 3 năm 2018, Nhân Đại Trung Quốc quyết định thành lập Bộ Cựu chiến binh, Phương Vĩnh Tường được bổ nhiệm làm Phó Bộ trưởng, Thành viên Đảng tổ bộ,[3] sang tháng 4 thì phân công kiêm nhiệm là Trợ lý Chủ nhiệm Bộ Công tác Chính trị Quân ủy Trung ương. Vào tháng 12 năm 2021, ông được điều động và nhậm chức Phó Tư lệnh Chiến khu Nam Bộ kiêm Chính ủy Lục quân Chiến khu Nam Bộ, đồng thời được thăng quân hàm là Trung tướng.[4] Giai đoạn đầu năm 2022, ông được bầu làm đại biểu tham gia Đại hội Đảng Cộng sản Trung Quốc lần thứ XX từ đoàn Quân Giải phóng và Vũ cảnh.[5][6] Trong quá trình bầu cử tại đại hội,[7][8][9] ông được bầu là Ủy viên dự khuyết Ủy ban Trung ương Đảng Cộng sản Trung Quốc khóa XX.[10][11]